§1.1 Field of the Invention
The invention concerns the establishment of label-switched paths (LSPs). More specifically, the invention concerns using a label distribution protocol (LDP) in which forwarding equivalency class (FEC) elements having external prefixes or external host addresses may be used.
§1.2 Description of Related Art
The description of art in this section is not an admission that such art is prior art. Although one skilled in the art will be familiar with networking, LSPs, and protocols such as RFC 3036 LDP, each is briefly introduced below for the convenience of the less experienced reader. More specifically, the need for LSPs, as well as their operation and establishment, are introduced in §§1.2.1-1.2.3 below.
§1.2.1 The Need for Label-Switched Paths
Circuit-switched networks establish a connection between hosts (parties to a communication) for the duration of their communication (“call”). The public-switched telephone network (PSTN) is an example of a circuit-switched network, where parties to a call are provided with a connection for the duration of the call. Unfortunately, for many communications applications circuit-switched networks use network resources inefficiently. Consider, for example, the communications of short, infrequent “bursts” of data between hosts. Providing a connection for the duration of a call between such hosts simply wastes communications resources when no data is being transferred. Such inefficiencies are not a problem in packet-switched networks.
Packet-switched networks are typically made up of interconnected nodes (referred to as “routers” in the specification below, without loss of generality) for forwarding addressed data (referred to as “packets” in the specification below without loss of generality). Packets traverse the network by being forwarded from router to router until they reach their destinations, which are typically specified by so-called layer-3 addresses in the packet headers. Unlike switches, however, routers determine the destination addresses of received packets and, based on these destination addresses, determine the appropriate link on which to send them. Routers may use protocols to discover the topology of the network, and algorithms to determine the most efficient ways to forward packets towards a particular destination address or addresses. Since the network topology can change, packets destined for the same address may be routed differently. Such packets can even arrive out of sequence.
In some cases it may be considered desirable to establish a fixed path through at least a part of a packet-switched network for at least some packets. Such paths can be engineered to account for bandwidth availability and traffic characteristics. Traffic engineering permits network administrators to map traffic flows onto an existing physical topology. In this way, network administrators can move traffic flows away from congested shortest paths to a less congested path, or paths. Alternatively, paths can be determined autonomously, even on demand.
Label-switching can be used to establish a fixed LSP from a head-end node (e.g., an ingress router) to a tail-end node (e.g., an egress router). The LSP may be determined using known protocols. Once an LSP is determined, each router in the path may be configured manually, or via some signaling mechanism to forward packets to a peer (e.g., a “downstream” or “upstream” neighbor) router in the path. Routers in the path determine that a given set of packets (e.g., a flow) are to be sent over the fixed path (as opposed to being routed individually) based on unique labels added to the packets. Analogs of LSPs can also be used in circuit-switched networks. For example, generalized multiprotocol label switching (GMPLS) can be used in circuit-switched networks having switches, optical cross-connects, SON ET/SDH cross-connects, etc. In multiprotocol label switching (MPLS), a label is provided explicitly in the data. However, in GMPLS, a label to be associated with data can be provided explicitly in the data, or can be inferred from something external to the data, such as a port on which the data was received, or a time slot or wavelength in which the data was carried, for example.
§1.2.2 Operations of LSPs
The operation of forwarding a packet to a next hop based on address information can be thought of as two steps—partitioning the entire set of possible packets into a set of FECs, and mapping each FEC to a next hop. From a forwarding standpoint, packets mapped to the same FEC are indistinguishable. With MPLS, which is one LSP technique, a particular packet is assigned to a particular FEC just once, as the packet enters the label-switched part of the network, referred to as the “label-switched domain.” The FEC to which the packet is assigned is encoded as a label, typically a short, fixed length value. Thus, at subsequent nodes no further header analysis need be done—all subsequent forwarding over the label-switched domain is driven by the labels.
FIG. 1 illustrates LSP 110 across a network. Like LSP 110, LSPs are, in general, simplex—traffic flows in one direction from a head-end (H-E) label-switching router (LSR) 120 at an ingress edge to a tail-end (T-E) LSR 130 at an egress edge. Generally, duplex traffic requires two LSPs—one for each direction. However, some protocols support bi-directional LSPs. Notice that LSP 110 is defined by the concatenation of one or more label-switched hops, allowing a packet to be forwarded from one LSR to another across the LSP 110.
Recall that a label may be a short, fixed-length value carried in a packet's header used to identify a FEC. Alternatively, the label may be inferred from something external to the data, such as the port number on which the data was received (e.g., in the case of optical cross-connects), or the time slot in which the data was carried (e.g., in the case of SONET/SDH cross connects) of addressed data or of a cell. Recall further that, in the context of an LSP, a FEC may define a set of packets (or more generally data) that are forwarded over the same path through a network, sometimes even if their ultimate destinations are different. At the ingress edge of the network, each packet is assigned an initial label (e.g., based on all or a part of its layer 3 destination address). More specifically, referring to the example illustrated in FIG. 2, a H-E LSR 210 may interpret the destination address 220 of an unlabeled packet, perform a longest-match routing table lookup, map the packet to an FEC, assign a label 230 to the packet and forward it to the next hop in the LSP.
In the MPLS domain defined by the LSP, LSRs 220 ignore the packet's network layer header and simply forward the packet using label-swapping. More specifically, when a labeled packet arrives at an LSR, the input port number and the label are used as lookup keys into an MPLS forwarding table. When a match is found, the forwarding component retrieves the associated outgoing label, the outgoing interface (or port), and the next hop address from the forwarding table. The incoming label is replaced with the outgoing label and the packet is directed to the outgoing interface for transmission to the next hop in the LSP. FIG. 2 illustrates such label-switching by LSRs 220a and 220b. 
When the labeled packet arrives at T-E LSR 240, if the next hop is not an LSR, T-E LSR 240 discards (“pops”) the label and forwards the packet using conventional longest-match IP forwarding. FIG. 2 illustrates such label discarding and IP forwarding by T-E LSR 240.
§1.2.3 Establishing LSPs Using LDP
In the example illustrated with reference to FIG. 2, each LSR had appropriate forwarding labels. These labels may be provided to the LSRs using various protocols that are available, or that have been proposed for signaling labels. An example of one such protocol, LDP, is described in “LDP Specification,” Request for Comments: 3036, the Internet Engineering Task Force (January 2001) (Incorporated herein by reference and referred to below as “RFC 3036”). With LDP-signaled LSPs, nodes establish LSPs through a network by mapping network-layer routing information directly to LSPs. More specifically, LDP associates a set of destinations, defined by route prefixes and/or router addresses with each data link LSP. This set of destinations is called the FEC. These destinations all share a common data link LSP egress and a common unicast routing path. Each LSR chooses the label advertised by the next hop for the FEC and splices it to the label it advertises to all other LSRs. This forms a tree of LSPs that converge on the T-E LSR.
FIG. 3 illustrates the binding of a label to a FEC and the communication of such label binding information among peer nodes. In this example, suppose FEC “j” defines all packets that are destined for, or should pass through, IP address 219.1.1.1. Notice that each of the nodes may be thought of as including a control component 330 and a forwarding component 310. At the edge of the LSP 390, node 240′ assigns a label 3″ to FEC j. This association is stored as label information 340c, as indicated by 350. Furthermore, this association is communicated to upstream node (also referred to as a “peer” or “neighbor” node) 220b′ as indicated by communication 352. Node 220b′ assigns its own label “100” to FEC j. This binding is similarly stored as label information 340b. Further, using the FEC j, node 220b′ binds its label “100” to the received label “3”, and stores them as an IN label 322b and an OUT label 324b forwarding information 320b, as indicated by 354. Furthermore, its 220b′ association is communicated to upstream node (also referred to as a “peer” or “neighbor” node) 220a′ as indicated by communication 356.
Node 220a′ assigns its own label “500” to FEC j. This binding is similarly stored as label information 340a. Further, using FEC j, node 220a′ binds its label “500” to the received label “100”, and stores them as an IN label 322a and an OUT label 324a forwarding information 320a, as indicated by 358. Furthermore, its 220a′ association is communicated to an upstream node (not shown) as indicated by communication 359.
This process of using the FEC to bind a label with a received label, as well as communicating a label to a peer or neighbor node, results in the establishment of an LSP, such as that illustrated in FIG. 2.
RFC 3036 describes label mapping message procedures in §3.5.7.1. In particular, this section specifies that an LSR receiving a label mapping message from a downstream LSR for a Prefix or Host Address FEC Element should not use the label for forwarding unless its routing table contains an entry that exactly matches the FEC element. This may be provided to ensure that the LDP LSP will follow the shortest path calculated by a routing protocol, and to ensure that there will be no routing loops. This requirement is not a problem when the LSP is within a single network domain (or a single autonomous system (AS)), such as the case illustrated in FIG. 4 in which an LSP is provided between provider edge devices (PE) 420, 430 in a network domain 410, to provide virtual private network (VPN) services to customer edge devices (CE) 425, 435 for example.
However, consider a case as illustrated in FIG. 5 in which an LSP is included in more than one AS 510, 520, 530. This situation may arise either in a multi-provider scenario, or in the case where a single provider has several ASs. LDP and a border gateway protocol (BGP) could be used to signal labels. However, routing information known by nodes in AS 510 might not include information about nodes in AS 520 or AS 530. The routing information could be updated to include information about nodes in other ASs (e.g., routes for LDP FECs could be injected into an IGP), but this may be undesirable. For example, in a multi-AS topology, an service provider (“SP”) may not want to advertise a PE's addresses into the local IGP. Rather than using LDP and BGP, a resource reservation protocol (RSVP) could be used end-to-end. However, end-to-end RSVP is not standard and is not as scalable. Further, many network service providers are already running LDP in their networks. Another alternative solution is to use end-to-end BGP. However, this requires a three-label stack (e.g., 500:900:PE1 and some customer hardware does not support three label stacks.
In view of the foregoing, it may be desirable to allow LDP-signaled LSPs without requiring information about remote ASs (e.g., FEC element prefixes or host addresses that are external to the IGP) to be injected into the local IGP.